A number of apparatus are known for producing volumetric data representations of an object. An example of such an apparatus is a CAT scanner which generates representations of an object by subjecting the object to radiant energy (specifically X-rays) across a cross-sectional slice of the object and by detecting the radiant energy transmitted through that slice of the object. The detected radiant energy varies depending upon the characteristics of the substances that make up the object in the area of the slice. Therefore, by analyzing the detected radiant energy, a two-dimensional array of sampled radiographic densities is formed. This two-dimensional array can be displayed as an image of the object at the cross-sectional slice. A three-dimensional sample of the entire object can be constructed by combining multiple slices generated successively across the entire length of the object. In this manner, the object is represented by a three-dimensional array of data indicating the characteristics of the substances that make up the volume of the object.
Although the volumetric representation of an object is useful for many applications, it cannot interface directly with many computer aided design (CAD) or CAM systems. Most modern CAD/CAM systems receive input data in the form of geometric primitives, such as points, lines, arcs, b-spline (NURB) curves, planes, conics and b-spline (NURB) surfaces. Since the volumetric representations generated by a CAT scanner and other similar apparatus do not define the scanned object in terms of geometric primitives, these apparatus cannot interface directly with many modern CAD/CAM systems.
It is desirable to develop a method and apparatus for converting a volumetric data representation of an object into a collection of geometric primitives that constitute a single solid model representation which is more useful for certain applications, including interfacing with CAD/CAM systems. Two techniques have been developed for converting a volumetric data representation of an object into a solid model of the object. First, a method known as the polygonal method has been developed which attempts to model an object defined in volumetric data by a series of polygons, such as triangles. Initially, a series of polygons is formed that encloses the object volume. Thereafter, the method determines the area where the greatest difference exists between the polygon model and the object volume, and the polygon covering that area is sub-divided into smaller polygons. In this manner, the polygon model is continually sub-divided into greater numbers of polygons and the accuracy of the polygon model increases with each sub-division. This method is often used in graphics applications and generates an accurate representation when a close examination is conducted for small portions of the object surface. However, the polygon model generated from this method consists of a series of discrete entities and does not have any topological understanding. The model generated by the polygonal method is not a single contiguous solid model and therefore, it cannot be used for many applications such as interfacing with certain CAD/CAM systems.
A second method for modeling volumetric data is known as the contour or perimeter method. This method looks at each slice of volumetric data individually and models the shape of the object as defined on each slice. Thereafter, the model for each of the slices is combined together to form a model of the entire object. Since each slice is modeled individually, this method also results in a model having a plurality of discrete components. Therefore, this model does not generate a single contiguous solid model of the object and cannot be utilized effectively for certain applications. Additionally, this method cannot model multiple contours defined on any one slice.
Accordingly it is an object of the present invention to provide a method and apparatus for generating a NURB based solid model representation of an object represented in terms of volumetric data that can be used to drive a CAD/CAM system or for various other uses.